#include "hash_map.h"

#include <stdio.h>

void hash_table_init(const char* filename, BufferPool* pool, off_t n_directory_blocks) {
    short i = 0, j = 0;

    /**
     * init buffer pool
     */
    init_buffer_pool(filename, pool);
    
    /**
     * if file length is not 0, do not init  
     */
    if(pool->file.length != 0)
        return;

    /**
     * init control block
     */
    HashMapControlBlock* ctl = (HashMapControlBlock*)get_page(pool, 0);
    
    ctl->free_block_head = 0;
    ctl->n_directory_blocks = PAGE_SIZE / HASH_MAP_DIR_BLOCK_SIZE;
    ctl->max_size = PAGE_SIZE;

    /**
     * init directory block
     */
    for (i = 0; i < ctl->n_directory_blocks; i++) {
        HashMapDirectoryBlock* dir = (HashMapDirectoryBlock*)get_page(pool, (i + 1) * PAGE_SIZE);
        for (j = 0; j < HASH_MAP_DIR_BLOCK_SIZE; j++)
            dir->directory[j] = 0;
        release(pool, (i + 1) * PAGE_SIZE);
    }

    /**
     * page release
     */
    release(pool, 0);
}

void hash_table_close(BufferPool* pool) {
    /**
     * close buffer pool
     */
    close_buffer_pool(pool);
}

void hash_table_insert(BufferPool* pool, short size, off_t addr) {
    short i = 0;

    /**
     * get ctl-block & dir-block
     */
    short beg_page = size / HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ n_directory_blocks - 1
    short beg_page_item = size % HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ HASH_MAP_DIR_BLOCK_SIZE - 1
    HashMapControlBlock* ctl = (HashMapControlBlock*)get_page(pool, 0); 
    HashMapDirectoryBlock* dir = (HashMapDirectoryBlock*)get_page(pool, (beg_page + 1) * PAGE_SIZE); 

    /**
     * get con-block & insert
     */
    off_t block_addr = 0, block_addr_nxt = 0;
    HashMapBlock* block = NULL, *block_nxt = NULL;
    // deal with first block
    if (dir->directory[beg_page_item] == 0) { // empty, need new page
        if (ctl->free_block_head == 0) { // empty
            block_addr = pool->file.length; // new page
            block = (HashMapBlock*)get_page(pool, block_addr); 
            block->next = 0;
            block->n_items = 1;
            block->table[0] = addr;
            dir->directory[beg_page_item] = block_addr;
            release(pool, block_addr); 
        }
        else {
            block_addr = ctl->free_block_head;
            block = (HashMapBlock*)get_page(pool, block_addr); 
            ctl->free_block_head = block->next;
            block->next = 0;
            block->n_items = 1;
            block->table[0] = addr;
            dir->directory[beg_page_item] = block_addr;
            release(pool, block_addr); 
        }
    }
    else { // has page
        block_addr = dir->directory[beg_page_item];
        block = (HashMapBlock*)get_page(pool, block_addr); 
        while (block->n_items == HASH_MAP_BLOCK_SIZE && block->next != 0) { // find first available space
            release(pool, block_addr); 
            block_addr = block->next;
            block = (HashMapBlock*)get_page(pool, block_addr); 
        }
        if (block->n_items == HASH_MAP_BLOCK_SIZE) { // full, need new page
            if (ctl->free_block_head == 0) { // empty
                block_addr_nxt = pool->file.length; // new page
                block_nxt = (HashMapBlock*)get_page(pool, block_addr_nxt); 
                block_nxt->next = 0;
                block_nxt->n_items = 1;
                block_nxt->table[0] = addr;
                block->next = block_addr_nxt;
                release(pool, block_addr);  
                release(pool, block_addr_nxt); 
            }
            else {
                block_addr_nxt = ctl->free_block_head;
                block_nxt = (HashMapBlock*)get_page(pool, block_addr_nxt); 
                ctl->free_block_head = block_nxt->next;
                block_nxt->next = 0;
                block_nxt->n_items = 1;
                block_nxt->table[0] = addr;
                block->next = block_addr_nxt;
                release(pool, block_addr);  
                release(pool, block_addr_nxt); 
            }
        }
        else { // have available space
            block->table[block->n_items] = addr;
            block->n_items++;
            release(pool, block_addr); 
        }
    }

    /**
     * release ctl-block & dir-block
     */
    release(pool, (beg_page + 1) * PAGE_SIZE); 
    release(pool, 0); 

} 

off_t hash_table_pop_lower_bound(BufferPool* pool, short size) {
    short i = 0, j = 0, hit = 0, pos_page = 0, pos_item = 0;

    /**
     * get ctl-block
     */
    HashMapControlBlock* ctl = (HashMapControlBlock*)get_page(pool, 0); 

    /**
     * git dir-block
     */
    short beg_page = size / HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ n_directory_blocks - 1
    short beg_page_item = size % HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ HASH_MAP_DIR_BLOCK_SIZE - 1
    HashMapDirectoryBlock* dir = NULL;
    for (i = beg_page; i < ctl->n_directory_blocks; i++) {
        dir = (HashMapDirectoryBlock*)get_page(pool, (i + 1) * PAGE_SIZE); 
        for (j = (i == beg_page) ? beg_page_item : 0; j < HASH_MAP_DIR_BLOCK_SIZE; j++) {
            if (dir->directory[j] != 0) {
                hit = 1;
                pos_page = i;
                pos_item = j;
                break;
            }
        }
        if (hit) break;
        else release(pool, (i + 1) * PAGE_SIZE); 
    }
    if (!hit) {
        release(pool, 0); 

        return -1;
    }

    /**
     * search for qualified page if hit
     */
    off_t des_addr = 0;
    off_t addr = dir->directory[pos_item];
    HashMapBlock* block = (HashMapBlock*)get_page(pool, addr); 
    block->n_items--;
    des_addr = block->table[block->n_items];
    block->table[block->n_items] = 0;
    if (block->n_items == 0) { // become empty
        dir->directory[pos_item] = block->next;
        block->next = ctl->free_block_head;
        ctl->free_block_head = addr;
    }
    release(pool, addr); 

    /**
     * release ctl-block & dir-block
     */
    release(pool, (pos_page + 1) * PAGE_SIZE); 
    release(pool, 0); 

    return des_addr;
}

void hash_table_pop(BufferPool* pool, short size, off_t addr) {
    short i = 0, j = 0, hit = 0;

    /**
     * get ctl-block & dir-block & con-block
     */
    short beg_page = size / HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ n_directory_blocks - 1
    short beg_page_item = size % HASH_MAP_DIR_BLOCK_SIZE; // 0 ~ HASH_MAP_DIR_BLOCK_SIZE - 1
    HashMapControlBlock* ctl = (HashMapControlBlock*)get_page(pool, 0); 
    HashMapDirectoryBlock* dir = (HashMapDirectoryBlock*)get_page(pool, (beg_page + 1) * PAGE_SIZE); 

    /**
     * find addr to pop
     */
    off_t block_addr = 0, block_addr_nxt = 0;
    HashMapBlock* block = NULL, * block_nxt = NULL;
    // deal with first block
    if (dir->directory[beg_page_item] == 0) return; // invalid
    block_addr = dir->directory[beg_page_item];
    block = (HashMapBlock*)get_page(pool, block_addr); 
    for (i = 0; i < block->n_items; i++) { // find addr
        if (block->table[i] == addr) {
            hit = 1;
            for (j = i; j < block->n_items - 1; j++)
                block->table[j] = block->table[j + 1];
            block->table[block->n_items - 1] = 0;
            block->n_items--;
            if (block->n_items == 0) { // become empty
                dir->directory[beg_page_item] = block->next;
                block->next = ctl->free_block_head;
                ctl->free_block_head = block_addr;
            }
            release(pool, block_addr); 
            break;
        }
    }
    // deal with remaining blocks
    if (!hit) {
        while (block->next != 0) {
            block_addr_nxt = block->next;
            block_nxt = (HashMapBlock*)get_page(pool, block_addr_nxt); 
            for (i = 0; i < block_nxt->n_items; i++) { // find addr
                if (block_nxt->table[i] == addr) {
                    hit = 1;
                    for (j = i; j < block_nxt->n_items - 1; j++)
                        block_nxt->table[j] = block_nxt->table[j + 1];
                    block_nxt->table[block_nxt->n_items - 1] = 0;
                    block_nxt->n_items--;
                    if (block_nxt->n_items == 0) { // become empty
                        block->next = block_nxt->next;
                        block_nxt->next = ctl->free_block_head;
                        ctl->free_block_head = block_addr_nxt;
                    }
                    break;
                }
            }
            release(pool, block_addr); 
            if (hit) {
                release(pool, block_addr_nxt); 
                break;
            }
            else {
                block_addr = block_addr_nxt;
                block = block_nxt;              
            }
        }
        if(!hit) release(pool, block_addr);
    }

    /**
     * release ctl-block & dir-block
     */
    release(pool, (beg_page + 1) * PAGE_SIZE); 
    release(pool, 0); 

}

//  void print_hash_table(BufferPool *pool) {
//     HashMapControlBlock *ctrl = (HashMapControlBlock*)get_page(pool, 0);
//     HashMapDirectoryBlock *dir_block;
//     off_t block_addr, next_addr;
//     HashMapBlock *block;
//     int i, j;
//     printf("----------HASH TABLE----------\n");
//     for (i = 0; i < ctrl->max_size; ++i) {
//         dir_block = (HashMapDirectoryBlock*)get_page(pool, (i / HASH_MAP_DIR_BLOCK_SIZE + 1) * PAGE_SIZE);
//         if (dir_block->directory[i % HASH_MAP_DIR_BLOCK_SIZE] != 0) {
//             printf("%d:", i);
//             block_addr = dir_block->directory[i % HASH_MAP_DIR_BLOCK_SIZE];
//             while (block_addr != 0) {
//                 block = (HashMapBlock*)get_page(pool, block_addr);
//                 printf("  [" FORMAT_off_t "]", block_addr);
//                 printf("{");
//                 for (j = 0; j < block->n_items; ++j) {
//                     if (j != 0) {
//                         printf(", ");
//                     }
//                     printf(FORMAT_off_t, block->table[j]);
//                 }
//                 printf("}");
//                 next_addr = block->next;
//                 release(pool, block_addr);
//                 block_addr = next_addr;
//             }
//             printf("\n");
//         }
//         release(pool, (i / HASH_MAP_DIR_BLOCK_SIZE + 1) * PAGE_SIZE);
//     }
//     release(pool, 0);
//     printf("------------------------------\n");
// } 